package com.kevin.Code.OfferReviewVersion2;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author Vinlee Xiao
 * @Classname OfferII_119
 * @Description Leetcode 128 二刷同剑指OfferII 119 最长递增序列 中等难度
 * @Date 2022/1/22 13:55
 * @Version 1.0
 */
public class OfferII_119 {


    /**
     * 利用广度优先遍历
     * 题意理解错误
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        int longest = 0;
        //去重的作用
        for (int num : nums) {
            hashSet.add(num);
        }

        for (int num : nums) {
            if (hashSet.contains(num)) {
                int result = bfs(nums, hashSet, num);
                longest = Math.max(longest, result);
            }
        }
        return longest;
    }

    /**
     * 广度优先遍历
     *
     * @param nums
     * @param hashSet
     * @return
     */
    private int bfs(int[] nums, HashSet<Integer> hashSet, int num) {
        //建立一个队列
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(num);
        //防止重复访问
        hashSet.remove(num);
        //初始化 currentLength的长度 因为本身num的长度为1
        int currentLength = 1;

        while (!deque.isEmpty()) {
            //
            int n = deque.pollFirst();
            //前后方向
            int[] neighbors = new int[]{n - 1, n + 1};
            for (int neighbor : neighbors) {
                if (hashSet.contains(neighbor)) {
                    //防止重复访问
                    hashSet.remove(neighbor);
                    deque.addLast(neighbor);
                    currentLength++;
                }
            }
        }
        return currentLength;
    }
}
